#include<vector>
#include<algorithm>
using namespace std;


class Solution {
private:
    int quickSelect2(vector<int>& nums, int start, int end, int k) {
        if (start >= end) return -1;
        int priv = start;
        int left = start + 1;
        int right = end - 1;
        while (left <= right) {
            if (nums[left] <= nums[priv])
                ++left;
            else
                swap(nums[right--], nums[left]);
        }
        swap(nums[right], nums[priv]);
        if (right < k) return quickSelect(nums, right + 1, end, k);
        else if (right > k) return quickSelect(nums, start, right, k);
        return nums[right];
    }

    int quickSelect(vector<int>&nums,int start,int end, int k) {
        if (start >= end) return -1;
        int priv = start;
        int left = start + 1;
        int right = end-1;
        while (left <= right) {
            while (left <= right && nums[left] <= nums[priv]) ++left;
            while (left <= right && nums[right] > nums[priv])--right;
            if (left < right)
                swap(nums[left], nums[right]);
        }
        swap(nums[right], nums[priv]);
        if (right < k) return quickSelect(nums, right + 1, end, k);
        else if (right > k) return quickSelect(nums, start, right, k);
        return nums[right];
    }

    void threePath(vector<int>& nums, int priv,int & start,int& end) {
        int left = 0, mid = 0, right = nums.size() - 1;
        while (left <= right) {
            while (left <= right&&nums[left] <= priv) {
                if (nums[left] < priv) {
                    if(mid < left)
                        swap(nums[mid], nums[left]);
                    ++mid;
                }
                ++left;
            }
            while (left <= right&&nums[right] > priv)
                --right;
            if (left <= right) 
                swap(nums[left], nums[right]);
        }
        start = mid;
        end = left;
    }

    void threePath2(vector<int>& nums, int priv, int& start, int& end) {
        int left = 0, mid = 0, right = nums.size() - 1;
        while (left <= right) {
            if (nums[left] < priv) {
                swap(nums[mid++], nums[left++]);
            }
            else if (nums[left] == priv) {
                ++left;
            }
            else {
                swap(nums[left], nums[right--]);
            }
        }
        start = mid;
        end = left;
    }


public:
    void wiggleSort(vector<int>& nums) {
        vector<int> nums_(nums);
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        //int n=quickSelect2(nums_,0,nums.size(), nums.size() / 2);
        int left, right;
        threePath2(nums_, nums[nums.size() / 2], left, right);
        left = (nums_.size() + 1) / 2 - 1;
        right = nums.size() - 1;
        int index = 0;
        while (index < nums.size()) {
            if (index % 2 == 0) {
                nums[index] = nums_[left--];
            }
            else {
                nums[index] = nums_[right--];
            }
            ++index;
        }
    }
};



//class Solution {
//public:
//    void wiggleSort(vector<int>& nums) {
//        vector<int> nums_ = nums;
//        sort(nums_.begin(), nums_.end());
//        int left = 0, right = nums_.size();
//        left = left + (right - left+1) / 2 - 1;
//        right -= 1;
//        int index = 0;
//        while (index < nums.size()) {
//            if (index % 2 == 0) {
//                nums[index++]=nums_[left--];
//            }
//            else {
//                nums[index++] = nums_[right--];
//            }
//        }
//    }
//};

//int main() {
//    Solution sol;
//    vector<int>nums = { 1,1,2,2,2,1 };
//    sol.wiggleSort(nums);
//
//}